package com.smdk.dsminio.utils;
import cn.hutool.core.util.StrUtil;
import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
  * 带虚拟节点的一致性Hash算法
  */
 public class ConsistentHashingWithoutVirtualNode {
  
     //待添加入Hash环的服务器列表(真实节点计算已经按照空间分布所以此server节点填写本机IP或者服务名称即可)
    // public static String[] servers = null;



    //真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
     private static List<String> realNodes = new LinkedList<>();
      
     //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
     public static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
              
     //虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应256个虚拟节点
     private static final int VIRTUAL_NODES = 256;
     //二级虚拟节点
     private static final int VIRTUAL_CHILD_NODES = 256;
     //初始化Node节点
     public static void init(String[] servers){
        //先把原始的服务器添加到真实结点列表中
        for(int i=0; i<servers.length; i++){
            realNodes.add(servers[i]);
        }

        //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高(双向虚拟节点 一个外层 一个内层)
        for (String str : realNodes){
            for(int i=0; i<VIRTUAL_NODES; i++){
                for (int j = 0; j <VIRTUAL_CHILD_NODES ; j++) {
                    String virtualNodeName = str + "&&NODEA" +i+"&&NODEB"+j+"&&";
                    int hash = getHash(virtualNodeName);
                    virtualNodes.put(hash, virtualNodeName);

                }
            }
        }
     }

     //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
     private static int getHash(String str){
         final int p = 16777619;
         int hash = (int)2166136261L;
         for (int i = 0; i < str.length(); i++) {
             hash = (hash ^ str.charAt(i)) * p;
         }
         hash += hash << 13;
         hash ^= hash >> 7;
         hash += hash << 3;
         hash ^= hash >> 17;
         hash += hash << 5;
          
         // 如果算出来的值为负数则取其绝对值
         if (hash < 0) {
             hash = Math.abs(hash);
         }
         return hash;
     }
      
     //得到应当路由到的结点
     public static String getServer(String key){
        //得到该key的hash值
         int hash = getHash(key);
         // 得到大于该Hash值的所有Map
         SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
         String virtualNode;
         if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
         }else{
            //第一个Key就是顺时针过去离node最近的那个节点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
         }
         //virtualNode虚拟节点名称要截取一下
         if(StrUtil.isNotBlank(virtualNode)){
             // return virtualNode.substring(0, virtualNode.indexOf("&&"));
             return virtualNode;
         }
         return null;
     }
    public static void main(String[] args) {
        String[] keys = {"太阳"};
        for (int i = 0; i < keys.length; i++) {
            System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i]) + ",被路由到结点[" + getServer(keys[i]) + "]");
        }
        String[] keyse = {"哈哈"};
        for (int i = 0; i < keyse.length; i++) {
            System.out.println("[" + keyse[i] + "]的hash值为" + getHash(keyse[i]) + ",被路由到结点[" + getServer(keyse[i]) + "]");
        }

        String[] keysf = {"啊啊啊"};
        for (int i = 0; i < keyse.length; i++) {
            System.out.println("[" + keysf[i] + "]的hash值为" + getHash(keysf[i]) + ",被路由到结点[" + getServer(keysf[i]) + "]");
        }

        String[] keysg = {"多福多寿"};
        for (int i = 0; i < keyse.length; i++) {
            System.out.println("[" + keysg[i] + "]的hash值为" + getHash(keysg[i]) + ",被路由到结点[" + getServer(keysg[i]) + "]");
        }
    }

}